package 真题;/**
 * @author： li
 * @date： 2022-01-18 19:56
 * @version 1.0
 */

/*【问题描述】
给定序列(a1,a2,… ,an)=(1,2,…. ,n)，即ai = i。
小蓝将对这个序列进行m次操作，每次可能是将at,a2,… ,aq降序排列，或者将aqi,aqi+1,…… ,an升序排列。
请求出操作完成后的序列。
【输入格式】
输入的第一行包含两个整数n, m，分别表示序列的长度和操作次数。
接下来m行描述对序列的操作，其中第i行包含两个整数 pi, qi表示操作类型和参数。当pi=0时，表示将a1,a2, … ,aqi降序排列;
当pi=1时，表示将aqi,aqi+1,……,an升序排列。
【输出格式】
输出一行，包含n个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。
【样例输入】
3 3
0 3
1 2
0 2
【样例输出】
3 l 2
【样例说明】
原数列为(1,2,3)。
第1步后为(3,2,1)。
第2步后为(3,1,2)。
第3步后为(3,1,2)。与第2步操作后相同，因为前两个数已经是降序了。
【评测用例规模与约定】
对于30%的评测用例，n,m ≤1000;
对于60%的评测用例，n,m ≤ 5000;
对于所有评测用例，1≤n,m ≤100000，0≤ pi≤1，1≤ qi ≤n。
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.Scanner;

public class 双向排序_栈 {
//    static StreamTokenizer in=new StreamTokenizer (new BufferedReader(new InputStreamReader(System.in)));
//    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
//    static int in() throws IOException{
//        in.nextToken();
//        return(int)in.nval;
//    }
    public static void main(String[]args) throws IOException{
        Scanner sc =new Scanner(System.in);
//        int n=in();int m=in();
        int n=sc.nextInt();int m=sc.nextInt();
        int[]sta=new int[m];
        int cnt=0;
        while(m-->0){
//            int op=in();int mid=in();
            int op=sc.nextInt();int mid=sc.nextInt();
            {//维护栈
                if(op==0){
                    if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同
                    {
                        if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;//则进行第一轮比较，如果当前更大则弹出最后一个
                        else continue;//否则直接舍去当前指令，进入下一层循环
                    }
                    while(cnt-2>=0&&sta[cnt-2]<=mid) cnt-=2;//循环弹出
                }else{
                    if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同
                    {
                        if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;//则进行第一轮比较，如果当前更小则弹出最后一个
                        else continue;//否则直接舍去当前指令，进入下一层循环
                    }
                    while(cnt-2>=0&&sta[cnt-2]>=mid) cnt-=2;//循环弹出
                }
                sta[cnt++]=mid;//压入栈
            }
        }
        int l=1;
        int r=n;
        int[] ans=new int[n+1];
        //x从大到小，从外到内填数字
        int x=n;

        for(int i=0;i<cnt;i++){
            int mid=sta[i];
            if(i%2==1){
                mid=Math.min(r, mid);
                while(l<mid)ans[l++]=x--;
            }
            else {
                mid=Math.max(l, mid);
                while(r>mid)ans[r--]=x--;
            }
            if(r-l<1)break;
        }
        if(l<=r)
            if(cnt%2==1) {
                while(l<=r)ans[l++]=x--;
            }else {
                while(l<=r)ans[r--]=x--;
            }
//        out.print(ans[1]);
//        for(int i=2;i<=n;i++) {
//            out.print(" "+ans[i]);
//        }
//        out.println();
//        out.flush();
        for(int i=1;i<=n;i++) {
            System.out.print(ans[i]+" ");
        }
    }
}

